package leetcode.problems.P300最长递增子序列;

public class LengthOfLIS {
}

// DP
//class Solution {
//    public int lengthOfLIS(int[] nums) {
//        int n = nums.length, maxLen = 1;
//        int[] dp = new int[n + 1];
//        for (int i = 0; i < n; ++i) {
//            dp[i] = 1;
//            for (int j = 0; j < i; ++j) {
//                if (nums[i] > nums[j]) {
//                    dp[i] = Math.max(dp[j] + 1, dp[i]);
//                    maxLen = Math.max(maxLen, dp[i]);
//                }
//            }
//        }
//        return maxLen;
//    }
//}

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length, maxLen = 1;
        int[] xLenMinElem = new int[n + 1];
        xLenMinElem[1] = nums[0];
        for (int i = 1; i < n; i++) {
            int elem = nums[i];
            if (elem > xLenMinElem[maxLen]) {
                xLenMinElem[++maxLen] = elem;
            } else {// 二分查找 elem在xLenMinElem中的位置
                int left = 1, right = maxLen, pos = 0;
                while (left <= right) {
                    int mid = right - (right - left) / 2;
                    if (xLenMinElem[mid] < elem) {
                        left = mid + 1;
                        pos = mid;
                    } else {
                        right = mid - 1;
                    }
                }
                xLenMinElem[pos + 1] = elem;
            }
        }
        return maxLen;
    }
}